package com.yhy;

import java.util.*;

/**
 * describe:
 *
 * @author helloworldyu
 * @data 2017/11/17
 */
public class PathImpl implements IPath {
	/**
	 * 存放每个点到源点的距离
	 */
	private IGraph graph = null;

	/**
	 * 遍历的源点
	 */
	public PathImpl(IGraph graph) {
		if (!Util.isNotNull(graph)) {
			throw new IllegalArgumentException("graph 不能为 null");
		}

		this.graph = graph;
	}


	/**
	 * 从队列中取点遍历。遍历的点的邻点全部添加到队列中。加入队列的一定会被遍历所以加入队列的 visted 设置为 true
	 *
	 * @param vertex
	 */
	@Override
	public void bfs(Vertex vertex) {
		Vertex inGraph = graph.findInGraph(vertex);
		if (null == inGraph) {
			throw new RuntimeException("不在图中");
		} else {
			//引用指向图中点
			vertex = inGraph;
		}
		//存放待遍历的点
		Deque<Vertex> vertexDeque = new ArrayDeque<>();
		//1.先把遍历源点压入队列中
		vertex.setDistance(0);
		vertex.setParent(null);
		vertex.setVisted(true);
		vertexDeque.push(vertex);

		do {
			//3.从队列中取出一个
			Vertex first = vertexDeque.pop();
			//把一个点的邻点加入到队列中
			ArrayList<Vertex> adj = graph.getAdj(first);
			for (Vertex ver : adj) {
				//-------没有加入队列的---------
				if (!ver.isVisted()) {
					ver.setParent(first);
					ver.setDistance(first.getDistance()+1);
					ver.setVisted(true);
					vertexDeque.push(ver);
				}
			}
		}while (!vertexDeque.isEmpty());
	}


	@Override
	public void dfs(Vertex vertex) {
		Vertex inGraph = graph.findInGraph(vertex);
		if (null == inGraph) {
			throw new RuntimeException("不在图中");
		} else {
			//引用指向图中点
			vertex = inGraph;
		}

		//设置此点已经遍历
		vertex.setVisted(true);
		//首节点没有 parent,
		if (null == vertex.getParent()) {
			vertex.setDistance(0);
		} else {
			vertex.setDistance(vertex.getParent().getDistance() + 1);
		}
		//遍历所有的临边
		ArrayList<Vertex> adjs = graph.getAdj(vertex);
		for (Vertex adj : adjs) {
			if (!adj.isVisted()) {
				//设置此节点的父节点为 当前遍历节点
				adj.setParent(vertex);
				dfs(adj);
			}
		}

	}


	@Override
	public boolean hasPath(Vertex dst) {
		return dst.isVisted();
	}

	@Override
	public List<Vertex> path(Vertex dst) {
		Vertex inGraph = graph.findInGraph(dst);
		if (null == inGraph) {
			throw new RuntimeException("不在图中");
		}

		Deque<Vertex> path = new ArrayDeque<>();
		Vertex tmp = dst;
		do {
			path.push(tmp);
			tmp = tmp.getParent();
		} while (null != tmp);

		return new ArrayList<>(path);
	}
}